<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            KMP算法 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">KMP算法</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2020-05-13 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>3.8k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>16 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><p>之前大一的时候写过一篇关于KMP的博客，写的也是乱七八糟的，自己看着都费劲，最近看左神的书《程序员代码面试指南》有讲，重新学了一遍，感觉写的还是挺好的，这篇就不从0开始讲解<code>KMP</code>了，简单说一些要点，方便以后回顾</p>
<blockquote>
<p>我记得大一为了搞懂kmp好像花了挺长时间的，网上翻各种博客，搞了大半天吧，结果还是没咋搞清楚，前几天看书大概只花了一个小时左右就都搞清楚了，可能是左神写的比较好吧😂</p>
</blockquote>
<h2 id="next数组是什么？"><a href="#next数组是什么？" class="headerlink" title="next数组是什么？"></a>next数组是什么？</h2><p><code>kmp</code>最关键的地方就是这个<code>next</code>数组了，<code>next</code>数组就是各个子串的前缀后缀最大匹配（相等）长度，具体一点就是<code>next[i]</code>代表的就是子串<code>i</code>位置前字符（不包括<code>i</code>位置）的前后缀最大匹配长度</p>
<p>举个例子： 子串<code>abababc</code>  </p>
<p>next[3] = “aba” 的前后缀最大匹配长度 = 1 (开头的a和结尾的a匹配)</p>
<p>next[6]= “ababab” 的前后缀最大匹配长度 = 4 （开头的abab和结尾的abab匹配）</p>
<h2 id="next数组的作用？"><a href="#next数组的作用？" class="headerlink" title="next数组的作用？"></a>next数组的作用？</h2><p>他的作用其实就是在两个字符串比较失配的时候避免目标串回溯，常规的暴力匹配在字符失配的时候就会回退到首字符重新匹配，整体时间复杂度就是<code>O(m*n)</code>，而next数组就是为了避免回退，简单举一个例子</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200513/ugvgLhmyaeBr.png?imageslim"
                      alt="mark"
                ></p>
<p>用PPT简单的画了个图（PPT真好用），当匹配到<strong>母串和子串</strong><code>index=6</code>的位置时，发现两者的字符不相同，按照暴力匹配，下一步就是母串回溯到<code>index=1</code>也就是b字符位置，子串回溯到首字符，重新开始匹配，直到匹配到子串，或者匹配完母串所有子串，但是当我们有了<code>next</code>数组，我们的母串就不必再回退了，而子串也不必再回退到首字符了，图中的黄色下划线和绿色下划线代表的就是<strong>子串index=6</strong>位置前的最长前后缀匹配长度，也就是<code>ababab</code>的<strong>最长前后缀匹配字符</strong>，当子串index=6位置的字符匹配不上的时候我们我们就可以直接将<code>index</code>跳到<code>next[6]</code>，也就是将子串索引移动到index=4的位置，就变成下面这样</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200513/6sBvml0hXrr6.png?imageslim"
                      alt="mark"
                ></p>
<p>母串并没有回退，继续匹配<code>母串index=6</code>和子串<code>index=4</code>位置的元素，然后重复上面的过程</p>
<h2 id="为什么子串可以直接滑动next-i-步？"><a href="#为什么子串可以直接滑动next-i-步？" class="headerlink" title="为什么子串可以直接滑动next[i]步？"></a>为什么子串可以直接滑动next[i]步？</h2><p>前面我们知道了如何使用<code>next</code>数组，但是为什么子串可以一下子从滑动到<code>next[i]</code>位置呢？万一中间有能匹配的字符不就滑过了么？</p>
<p>我们假设在母串中间存在某一个位置能匹配出子串，且该位置在<strong>子串最长匹配后缀之前</strong>，也就是说这部分<strong>比当前的最长前后缀匹配长度还要长</strong>对应到下图就是黑色虚线框框出来的部分</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200513/EbC0E1JvbkHh.png?imageslim"
                      alt="mark"
                ></p>
<p>既然能从这个位置匹配出子串，那么说明我的<strong>子串的前缀</strong>和这一部分相等，同时，由于失配前子串和母串是完全匹配的，所以我<strong>子串的后缀</strong>和这一部分肯定也是相等的，诶？我子串前后缀都和这部分相等，那它肯定是我的匹配前后缀啊，但是这部分又比我的最长前后缀长度要长，是不是矛盾了？所以原假设是不成立的，不存在这样的位置！所以子串可以放心的滑到<code>next[i]</code>位置</p>
<h2 id="next数组如何求？"><a href="#next数组如何求？" class="headerlink" title="next数组如何求？"></a>next数组如何求？</h2><p>说了这么多next数组，那么next数组究竟怎么求呢？其实整个的求解过程有点像动态规划，有一些细节需要注意下</p>
<blockquote>
<p>想起来了再写</p>
</blockquote>
<h2 id="时间复杂度为什么是线性的？"><a href="#时间复杂度为什么是线性的？" class="headerlink" title="时间复杂度为什么是线性的？"></a>时间复杂度为什么是线性的？</h2><blockquote>
<p>想起来了再写</p>
</blockquote>
<h2 id="例题"><a href="#例题" class="headerlink" title="例题"></a>例题</h2><h3 id="28-实现-strStr"><a href="#28-实现-strStr" class="headerlink" title="28. 实现 strStr()"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/implement-strstr/" >28. 实现 strStr()<i class="fas fa-external-link-alt"></i></a></h3><p>实现 <a class="link"   target="_blank" rel="noopener" href="https://baike.baidu.com/item/strstr/811469" >strStr()<i class="fas fa-external-link-alt"></i></a> 函数。</p>
<p>给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  <strong>-1</strong>。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: haystack = <span class="string">&quot;hello&quot;</span>, needle = <span class="string">&quot;ll&quot;</span></span><br><span class="line">输出: <span class="number">2</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: haystack = <span class="string">&quot;aaaaa&quot;</span>, needle = <span class="string">&quot;bba&quot;</span></span><br><span class="line">输出: -<span class="number">1</span></span><br></pre></td></tr></table></figure>

<p><strong>说明:</strong></p>
<p>当 <code>needle</code> 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。</p>
<p>对于本题而言，当 <code>needle</code> 是空字符串时我们应当返回 0 。这与C语言的 <a class="link"   target="_blank" rel="noopener" href="https://baike.baidu.com/item/strstr/811469" >strstr()<i class="fas fa-external-link-alt"></i></a> 以及 Java的 <a class="link"   target="_blank" rel="noopener" href="https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf(java.lang.String)" >indexOf()<i class="fas fa-external-link-alt"></i></a> 定义相符。</p>
<p><strong>解法一</strong></p>
<p>标注的是简单，很多人都是直接调的API，但是我感觉没啥意义，所以这题应该直接上kmp</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">strStr</span><span class="params">(String haystack, String needle)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(needle==<span class="keyword">null</span> || needle.length()&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span>(haystack==<span class="keyword">null</span> ||haystack.length()&lt;=<span class="number">0</span>) <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span>[] next=getNext(needle);</span><br><span class="line">    <span class="keyword">int</span> tidx=<span class="number">0</span>,sidx=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (sidx&lt;haystack.length() &amp;&amp; tidx&lt;needle.length()) &#123;</span><br><span class="line">        <span class="keyword">if</span>(needle.charAt(tidx) == haystack.charAt(sidx))&#123;</span><br><span class="line">            tidx++;sidx++;</span><br><span class="line">            <span class="keyword">if</span>(tidx==needle.length())&#123;</span><br><span class="line">                <span class="keyword">return</span> sidx-tidx;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(next[tidx]==-<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="comment">//完全失配sidx需要后移</span></span><br><span class="line">            sidx++;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            tidx=next[tidx];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//求t的next</span></span><br><span class="line"><span class="comment">//abadabac</span></span><br><span class="line"><span class="comment">//ac</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] getNext(String t)&#123;</span><br><span class="line">    <span class="keyword">int</span>[] next= <span class="keyword">new</span> <span class="keyword">int</span>[t.length()];</span><br><span class="line">    next[<span class="number">0</span>]=-<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(t.length()&lt;=<span class="number">1</span>) <span class="keyword">return</span> next;</span><br><span class="line">    next[<span class="number">1</span>]=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>,right=<span class="number">2</span>;</span><br><span class="line">    <span class="keyword">while</span>(right&lt;t.length())&#123;</span><br><span class="line">        <span class="keyword">if</span>(t.charAt(left)==t.charAt(right-<span class="number">1</span>))&#123;</span><br><span class="line">            left++;</span><br><span class="line">            next[right++]=left;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(next[left]==-<span class="number">1</span>)&#123; <span class="comment">//无法匹配了</span></span><br><span class="line">            right++; <span class="comment">//next[right]=0</span></span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            left=next[left];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>没啥好说的，裸kmp</p>
<h3 id="459-重复的子字符串"><a href="#459-重复的子字符串" class="headerlink" title="459. 重复的子字符串"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/repeated-substring-pattern/" >459. 重复的子字符串<i class="fas fa-external-link-alt"></i></a></h3><p>给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;abab&quot;</span></span><br><span class="line"></span><br><span class="line">输出: True</span><br><span class="line"></span><br><span class="line">解释: 可由子字符串 <span class="string">&quot;ab&quot;</span> 重复两次构成。</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;aba&quot;</span></span><br><span class="line"></span><br><span class="line">输出: False</span><br></pre></td></tr></table></figure>

<p><strong>示例 3:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;abcabcabcabc&quot;</span></span><br><span class="line"></span><br><span class="line">输出: True</span><br><span class="line"></span><br><span class="line">解释: 可由子字符串 <span class="string">&quot;abc&quot;</span> 重复四次构成。 (或者子字符串 <span class="string">&quot;abcabc&quot;</span> 重复两次构成。)</span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>这题标注的也是简单，确实暴力的解法不难想到，但是复杂度比较高，所以就直接上kmp</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="comment">//20ms，做复杂了，构造了一个s+s然后去掉头，再在里面kmp找</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">repeatedSubstringPattern</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(s==<span class="keyword">null</span> || s.length()&lt;=<span class="number">0</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    String t=s+s;</span><br><span class="line">    <span class="keyword">int</span>[] next=getNext(s);</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>,j=<span class="number">1</span>; <span class="comment">//去掉头</span></span><br><span class="line">    <span class="keyword">while</span>(i&lt;s.length() &amp;&amp; j&lt;t.length())&#123;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(i)==t.charAt(j))&#123;</span><br><span class="line">            i++;j++;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(next[i]==-<span class="number">1</span>)&#123;</span><br><span class="line">            j++;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            i=next[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> j-i!=s.length();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] getNext(String s)&#123;</span><br><span class="line">    <span class="keyword">if</span>(s.length()==<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;-<span class="number">1</span>&#125;;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] next=<span class="keyword">new</span> <span class="keyword">int</span>[s.length()];</span><br><span class="line">    next[<span class="number">0</span>]=-<span class="number">1</span>;</span><br><span class="line">    next[<span class="number">1</span>]=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>,right=<span class="number">2</span>; </span><br><span class="line">    <span class="keyword">while</span>(right&lt;s.length())&#123;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(left)==s.charAt(right-<span class="number">1</span>))&#123;</span><br><span class="line">            next[right++]=++left;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(next[left]==-<span class="number">1</span>)&#123;</span><br><span class="line">            next[right++]=<span class="number">0</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            left=next[left];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这个解法其实构造了一个<code>s+s</code>的字符<code>t</code>，然后去掉头，在<code>t[1:]</code>中找原<code>s</code>，最后找到的位置只要不是<code>s+s</code>连接处，也就是<code>s.length()</code>位置，那么就肯定是重复的有循环的，其实这个结论在写的时候并没有证明，完全是猜的😂，简单证明下，一图胜前言</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200513/O4Nmz343e9Li.png?imageslim"
                      alt="mark"
                ></p>
<p><strong>解法二</strong></p>
<p>其实只需要构造next数组，根据next数组就可以判断是不是重复的，我们看几组数据</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">   s:  a b c a b c a b c a b c \<span class="number">0</span></span><br><span class="line">next: -<span class="number">1</span> <span class="number">0</span> <span class="number">0</span> <span class="number">0</span> <span class="number">1</span> <span class="number">2</span> <span class="number">3</span> <span class="number">4</span> <span class="number">5</span> <span class="number">6</span> <span class="number">7</span> <span class="number">8</span>  <span class="number">9</span></span><br><span class="line">   s:  a a b a b d \<span class="number">0</span></span><br><span class="line">next: -<span class="number">1</span> <span class="number">0</span> <span class="number">1</span> <span class="number">0</span> <span class="number">1</span> <span class="number">0</span>  <span class="number">0</span></span><br><span class="line">   s:  a b c d a b \<span class="number">0</span></span><br><span class="line">next: -<span class="number">1</span> <span class="number">0</span> <span class="number">0</span> <span class="number">0</span> <span class="number">0</span> <span class="number">1</span> <span class="number">2</span> </span><br></pre></td></tr></table></figure>

<p>相比常规的KMP算法，我们在字符最后最后也加了<code>next</code>位，其实是为了区别下面的情况</p>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">   s:  a b a b \0</span><br><span class="line">next: -1 0 0 1 2</span><br><span class="line">   s:  a b a c \0</span><br><span class="line">next: -1 0 0 1 0</span><br></pre></td></tr></table></figure>

<p>然后我们就可以发现，next数组在过了一定的范围后就开始逐渐递增了，而这个递增的拐点就是在第一个循环节结束的时候，至于为什么我就不详细证明了，其实也很好想因为过了循环节，后面的都是和前面重复的，所以每多一个字符<code>next[i]=next[i-1]+1</code>，所以我们用字符的长度减去<code>next[slen]</code>就可以得到循环结的长度，我们只需要验证这个循环节能否被<code>s</code>字符串长度整除就可以了，同时需要防止循环节长度等于字符串长度的情况</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">repeatedSubstringPattern</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(s==<span class="keyword">null</span> || s.length()&lt;=<span class="number">1</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    <span class="keyword">int</span>[] next=getNext(s);</span><br><span class="line">    <span class="keyword">int</span> replen=s.length()-next[s.length()];</span><br><span class="line">    <span class="comment">//循环结长度等于字符长度</span></span><br><span class="line">    <span class="keyword">return</span> replen!=s.length() &amp;&amp; s.length()%replen==<span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] getNext(String s)&#123;</span><br><span class="line">    <span class="keyword">if</span>(s.length()==<span class="number">1</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;-<span class="number">1</span>&#125;;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span>[] next=<span class="keyword">new</span> <span class="keyword">int</span>[s.length()+<span class="number">1</span>];</span><br><span class="line">    next[<span class="number">0</span>]=-<span class="number">1</span>;</span><br><span class="line">    next[<span class="number">1</span>]=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>,right=<span class="number">2</span>; </span><br><span class="line">    <span class="keyword">while</span>(right&lt;=s.length())&#123;</span><br><span class="line">        <span class="keyword">if</span>(s.charAt(left)==s.charAt(right-<span class="number">1</span>))&#123;</span><br><span class="line">            next[right++]=++left;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(next[left]==-<span class="number">1</span>)&#123;</span><br><span class="line">            next[right++]=<span class="number">0</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            left=next[left];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>实在不行把这个记住就行了，反正我是记住了😂（过几天就忘了</p>
<h3 id="214-最短回文串"><a href="#214-最短回文串" class="headerlink" title="214. 最短回文串"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/shortest-palindrome/" >214. 最短回文串<i class="fas fa-external-link-alt"></i></a></h3><p>给定一个字符串 <strong><em>s</em></strong>，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;aacecaaa&quot;</span></span><br><span class="line">输出: <span class="string">&quot;aaacecaaa&quot;</span></span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入: <span class="string">&quot;abcd&quot;</span></span><br><span class="line">输出: <span class="string">&quot;dcbabcd&quot;</span></span><br></pre></td></tr></table></figure>

<p><strong>解法一</strong></p>
<p>这题很关键的一个点就是最短回文串其实就是原字符<code>s</code>，减去<code>s[0]</code>开头的最长回文串，剩下的部分再放到<code>s</code>前，这就是最短回文串</p>
<p>所以问题就变成了如何求<code>s[0]</code>开头的最长回文串，朴素的思路可以使用中心扩散法，枚举所有的字符和间隙，或者使用”马拉车”，等高效算法，这里不多介绍，主要介绍kmp的做法</p>
<p>我们把<code>s</code>串翻转变成<code>rs</code>，然后将两部分拼接起来变为<code>s+rs</code>，这个时候我们要求<code>s[0]</code>开头的最长回文子串，实际上就变成了求<code>s+rs</code>的最长公共前后缀</p>
<p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="http://static.imlgw.top/blog/20200518/CtFIYht31mIL.png?imageslim"
                      alt="mark"
                ></p>
<p>这里还有一点需要注意，就是<code>s+rs</code>的中间应该加分隔符，这是为了避免公共前后缀过长，甚至比原字符<code>s</code>还要长，这肯定是不对的，就比如<code>aaaaaaa</code>这样的case，加了分割符之后最长的前后缀就不会超过<code>s</code>了，</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> String <span class="title">shortestPalindrome</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    String rs=<span class="keyword">new</span> StringBuilder(s).reverse().toString();</span><br><span class="line">    <span class="comment">//#是为了避免前后缀过长超过原字符s的长度，比如aaaaaaa这种</span></span><br><span class="line">    String t=s+<span class="string">&quot;#&quot;</span>+rs; </span><br><span class="line">    <span class="keyword">int</span>[] next=<span class="keyword">new</span> <span class="keyword">int</span>[t.length()+<span class="number">1</span>];</span><br><span class="line">    next[<span class="number">0</span>]=-<span class="number">1</span>;</span><br><span class="line">    next[<span class="number">1</span>]=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> left=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">2</span>;</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=t.length())&#123;</span><br><span class="line">        <span class="keyword">if</span>(t.charAt(i-<span class="number">1</span>)==t.charAt(left))&#123;</span><br><span class="line">            next[i++]=++left;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(next[left]==-<span class="number">1</span>)&#123;</span><br><span class="line">            next[i++]=<span class="number">0</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            left=next[left];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//System.out.println(next[t.length()]);</span></span><br><span class="line">    <span class="keyword">return</span> rs.substring(<span class="number">0</span>,s.length()-next[t.length()])+s;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="1392-最长快乐前缀"><a href="#1392-最长快乐前缀" class="headerlink" title="1392. 最长快乐前缀"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/longest-happy-prefix/" >1392. 最长快乐前缀<i class="fas fa-external-link-alt"></i></a></h3><p>「快乐前缀」是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。</p>
<p>给你一个字符串 s，请你返回它的<strong>最长快乐前缀</strong>。</p>
<p>如果不存在满足题意的前缀，则返回一个空字符串。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;level&quot;</span></span><br><span class="line">输出：<span class="string">&quot;l&quot;</span></span><br><span class="line">解释：不包括 s 自己，一共有 <span class="number">4</span> 个前缀（<span class="string">&quot;l&quot;</span>, <span class="string">&quot;le&quot;</span>, <span class="string">&quot;lev&quot;</span>, <span class="string">&quot;leve&quot;</span>）和 <span class="number">4</span> 个后缀（<span class="string">&quot;l&quot;</span>, <span class="string">&quot;el&quot;</span>, <span class="string">&quot;vel&quot;</span>, <span class="string">&quot;evel&quot;</span>）。最长的既是前缀也是后缀的字符串是 <span class="string">&quot;l&quot;</span> 。</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p><strong>示例 2：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;ababab&quot;</span></span><br><span class="line">输出：<span class="string">&quot;abab&quot;</span></span><br><span class="line">解释：<span class="string">&quot;abab&quot;</span> 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。</span><br></pre></td></tr></table></figure>
<p><strong>示例 3：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;leetcodeleet&quot;</span></span><br><span class="line">输出：<span class="string">&quot;leet&quot;</span></span><br></pre></td></tr></table></figure>
<p><strong>示例 4：</strong></p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">输入：s = <span class="string">&quot;a&quot;</span></span><br><span class="line">输出：<span class="string">&quot;&quot;</span></span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li>1 &lt;= s.length &lt;= 10^5</li>
<li>s 只含有小写英文字母</li>
</ul>
<p><strong>解法一</strong></p>
<p>最近某次周赛的T4，没参加，今天看见群里有人提到了，看了下发现是裸KMP…正好复习下，结果写出bug了。。。</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">longestPrefix</span><span class="params">(s <span class="keyword">string</span>)</span> <span class="title">string</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> <span class="built_in">len</span>(s) == <span class="number">1</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&quot;&quot;</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//裸KMP</span></span><br><span class="line">    next := <span class="built_in">make</span>([]<span class="keyword">int</span>, <span class="built_in">len</span>(s)+<span class="number">1</span>)</span><br><span class="line">    next[<span class="number">0</span>] = <span class="number">-1</span></span><br><span class="line">    next[<span class="number">1</span>] = <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> left = <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> i = <span class="number">2</span></span><br><span class="line">    <span class="keyword">for</span> i &lt;= <span class="built_in">len</span>(s) &#123;</span><br><span class="line">        <span class="keyword">if</span> s[i<span class="number">-1</span>] == s[left] &#123;</span><br><span class="line">            left++</span><br><span class="line">            next[i] = left</span><br><span class="line">            i++</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> next[left] == <span class="number">-1</span> &#123;</span><br><span class="line">            i++</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            left = next[left]</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> s[<span class="number">0</span>:next[<span class="built_in">len</span>(s)]]</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>确实也长时间没有复习kmp了，kmp的细节几乎都忘了，上面的都是凭借着一点理解和记忆写的</p>
<blockquote>
<p>检查了前面kmp的写法，稍微改进了一下，目前统一了写法</p>
</blockquote>
<h3 id="796-旋转字符串"><a href="#796-旋转字符串" class="headerlink" title="796.旋转字符串"></a><a class="link"   target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/rotate-string/" >796.旋转字符串<i class="fas fa-external-link-alt"></i></a></h3><p>给定两个字符串, <code>A</code> 和 <code>B</code>。</p>
<p><code>A</code> 的旋转操作就是将 <code>A</code> 最左边的字符移动到最右边。 例如, 若 <code>A = &#39;abcde&#39;</code>，在移动一次之后结果就是<code>&#39;bcdea&#39;</code> 。如果在若干次旋转操作之后，<code>A</code> 能变成<code>B</code>，那么返回<code>True</code>。</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">示例 <span class="number">1</span>:</span><br><span class="line">输入: A = <span class="string">&#x27;abcde&#x27;</span>, B = <span class="string">&#x27;cdeab&#x27;</span></span><br><span class="line">输出: <span class="keyword">true</span></span><br></pre></td></tr></table></figure>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line">示例 <span class="number">2</span>:</span><br><span class="line">输入: A = <span class="string">&#x27;abcde&#x27;</span>, B = <span class="string">&#x27;abced&#x27;</span></span><br><span class="line">输出: <span class="keyword">false</span></span><br></pre></td></tr></table></figure>

<p><strong>注意：</strong></p>
<ul>
<li>  <code>A</code> 和 <code>B</code> 长度不超过 <code>100</code>。</li>
</ul>
<p><strong>解法一</strong></p>
<p>经典easy题当hard做，这个题数据量很小，直接暴力就行了，但是我们还是要追求更好的解法</p>
<p>一开始是在一篇文章中看到了这个题，里面说了这个题是kmp，我看了下没想到什么好的思路，只想到了一个NlogN的做法，二分+kmp找旋转点，然后kmp判断旋转点后时候也存在于A字符中（类似二分答案）</p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="comment">//不够聪明的做法: 二分+KMP 时间复杂度O(NlogN)</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">rotateString</span><span class="params">(A <span class="keyword">string</span>, B <span class="keyword">string</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> <span class="built_in">len</span>(A) != <span class="built_in">len</span>(B) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> A == B &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">var</span> left = <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> right = <span class="built_in">len</span>(B) - <span class="number">1</span></span><br><span class="line">    <span class="keyword">var</span> rotate = <span class="number">-1</span></span><br><span class="line">    <span class="comment">//二分找旋转点</span></span><br><span class="line">    <span class="keyword">for</span> left &lt;= right &#123;</span><br><span class="line">        mid := left + (right-left)/<span class="number">2</span></span><br><span class="line">        <span class="keyword">if</span> kmp(A, B[:mid+<span class="number">1</span>]) != <span class="number">-1</span> &#123;</span><br><span class="line">            rotate = mid</span><br><span class="line">            left++</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            right--</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> rotate == <span class="number">-1</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> kmp(A, B[rotate+<span class="number">1</span>:]) != <span class="number">-1</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">kmp</span><span class="params">(A <span class="keyword">string</span>, t <span class="keyword">string</span>)</span> <span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">var</span> next = getNext(t)</span><br><span class="line">    <span class="keyword">var</span> Ai = <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> ti = <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> Ai &lt; <span class="built_in">len</span>(A) &amp;&amp; ti &lt; <span class="built_in">len</span>(t) &#123;</span><br><span class="line">        <span class="keyword">if</span> A[Ai] == t[ti] &#123;</span><br><span class="line">            Ai++</span><br><span class="line">            ti++</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> next[ti] == <span class="number">-1</span> &#123;</span><br><span class="line">            Ai++</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            ti = next[ti]</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> ti == <span class="built_in">len</span>(t) &#123;</span><br><span class="line">        <span class="keyword">return</span> Ai - <span class="number">1</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">getNext</span><span class="params">(t <span class="keyword">string</span>)</span> []<span class="title">int</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> <span class="built_in">len</span>(t) &lt; <span class="number">2</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> []<span class="keyword">int</span>&#123;<span class="number">-1</span>&#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">var</span> next = <span class="built_in">make</span>([]<span class="keyword">int</span>, <span class="built_in">len</span>(t))</span><br><span class="line">    <span class="keyword">var</span> left = <span class="number">0</span></span><br><span class="line">    next[<span class="number">0</span>] = <span class="number">-1</span></span><br><span class="line">    next[<span class="number">1</span>] = <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> i = <span class="number">2</span></span><br><span class="line">    <span class="keyword">for</span> i &lt; <span class="built_in">len</span>(t) &#123;</span><br><span class="line">        <span class="keyword">if</span> t[left] == t[i<span class="number">-1</span>] &#123;</span><br><span class="line">            left++</span><br><span class="line">            next[i] = left</span><br><span class="line">            i++</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> next[left] == <span class="number">-1</span> &#123;</span><br><span class="line">            i++</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            left = next[left]</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> next</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>解法二</strong></p>
<p>看了评论区的大佬的做法，实际上<code>A+A</code>就包含了所有的旋转<code>A</code>的结果子串，<code>A+A</code>就相当于首位相连，所以我们可以直接在<code>A+A</code>中kmp找<code>B</code>就可以了，时间复杂度<code>O(N)</code></p>
<figure class="highlight golang"><table><tr><td class="code"><pre><span class="line"><span class="comment">//聪明的解法: A+A包含了所有可能的旋转情况，直接对A+A和B做kmp就行了</span></span><br><span class="line"><span class="comment">//abcdeabcde</span></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">rotateString</span><span class="params">(A <span class="keyword">string</span>, B <span class="keyword">string</span>)</span> <span class="title">bool</span></span> &#123;</span><br><span class="line">    <span class="keyword">if</span> <span class="built_in">len</span>(A) != <span class="built_in">len</span>(B) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> A == B &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> kmp(A+A, B) != <span class="number">-1</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：KMP算法</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2020-05-13 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2020/05/13/2da0528d/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2020/05/27/91d3cf25/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">Linux文件权限和目录配置</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2020/02/02/c517589e/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">并查集</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2020/05/13/2da0528d/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%89%8D%E8%A8%80"><span class="nav-number">1.</span> <span class="nav-text">前言</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#next%E6%95%B0%E7%BB%84%E6%98%AF%E4%BB%80%E4%B9%88%EF%BC%9F"><span class="nav-number">2.</span> <span class="nav-text">next数组是什么？</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#next%E6%95%B0%E7%BB%84%E7%9A%84%E4%BD%9C%E7%94%A8%EF%BC%9F"><span class="nav-number">3.</span> <span class="nav-text">next数组的作用？</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%B8%BA%E4%BB%80%E4%B9%88%E5%AD%90%E4%B8%B2%E5%8F%AF%E4%BB%A5%E7%9B%B4%E6%8E%A5%E6%BB%91%E5%8A%A8next-i-%E6%AD%A5%EF%BC%9F"><span class="nav-number">4.</span> <span class="nav-text">为什么子串可以直接滑动next[i]步？</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#next%E6%95%B0%E7%BB%84%E5%A6%82%E4%BD%95%E6%B1%82%EF%BC%9F"><span class="nav-number">5.</span> <span class="nav-text">next数组如何求？</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E4%B8%BA%E4%BB%80%E4%B9%88%E6%98%AF%E7%BA%BF%E6%80%A7%E7%9A%84%EF%BC%9F"><span class="nav-number">6.</span> <span class="nav-text">时间复杂度为什么是线性的？</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E4%BE%8B%E9%A2%98"><span class="nav-number">7.</span> <span class="nav-text">例题</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#28-%E5%AE%9E%E7%8E%B0-strStr"><span class="nav-number">7.1.</span> <span class="nav-text">28. 实现 strStr()</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#459-%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">7.2.</span> <span class="nav-text">459. 重复的子字符串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#214-%E6%9C%80%E7%9F%AD%E5%9B%9E%E6%96%87%E4%B8%B2"><span class="nav-number">7.3.</span> <span class="nav-text">214. 最短回文串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1392-%E6%9C%80%E9%95%BF%E5%BF%AB%E4%B9%90%E5%89%8D%E7%BC%80"><span class="nav-number">7.4.</span> <span class="nav-text">1392. 最长快乐前缀</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#796-%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">7.5.</span> <span class="nav-text">796.旋转字符串</span></a></li></ol></li></ol>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
